﻿// 202 迷宫.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <queue>


using  namespace std;
/*
http://oj.daimayuan.top/course/14/problem/631

有一个迷宫，每次只能往上下左右四个方向中的一个方向走一格，请算出从起点到终点的最短路径的长度。

迷宫用一个 n行 m列的字符矩阵表示，矩阵中存在 4种字符：

S 表示起点；
E 表示终点；
. 表示可以在上面移动的点；
X 表示障碍物。

输入格式
第一行两个整数 n,m，表示迷宫的大小。

接下来 n行，每行一个长度为 m的字符串。

数据保证起点和终点都只有一个。

输出格式
输出一行一个整数，表示最短路径的长度，如果不存在从起点到终点的路径输出 -1。

样例输入
3 3
SXE
.X.
...
样例输出
6
数据规模
对于所有数据，保证 2≤n,m≤1000。
*/

const int N = 1010;
char gra[N][N];
int vis[N][N];
int n, m;
int ans = 0;
int startx, starty;
int endx, endy;

int addx[] = { 1,-1,0,0 };
int addy[] = { 0,0,1,-1 };

void bfs() {
	queue<vector<int>> q;
	q.push({ startx,starty,0 });
	vis[startx][starty] = 1;

	while (!q.empty()) {
		auto e = q.front(); q.pop();
		if (e[0] == endx && e[1] == endy) {
			cout << e[2] << endl; return;
		}

		for (int i = 0; i < 4; i++) {
			int newx = e[0] + addx[i];
			int newy = e[1] + addy[i];
			if (newx >= 0 && newx < n && newy >= 0 && newy < m && vis[newx][newy] == 0&& gra[newx][newy]!= 'X') {
				q.push({ newx,newy,e[2] + 1 });
				vis[newx][newy] = 1;
			}
		}
	}

	cout << -1 << endl;
}

int main()
{
	cin >> n >> m;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> gra[i][j];
			if ('S' == gra[i][j]) {
				startx = i; starty = j;
			}
			else if ('E' == gra[i][j]) {
				endx = i, endy = j;
			}
		}
	}
	 
	bfs();

	return 0;
}

 